package com.yoshino.leetcode.improve40.seventeenth;

import java.util.HashMap;
import java.util.Map;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
class Solution {
    // 2.前缀和 + dfs
    int target, res;
    Map<Long, Integer> map = new HashMap<>();
    int maxSum = Integer.MIN_VALUE;

    // 1. 深度遍历
    public int pathSum2(TreeNode root, int targetSum) {
        // 深度
        if (root == null) {
            return 0;
        }
        return dfs(root, targetSum, 0) + pathSum(root.left, targetSum) + pathSum(root.right, targetSum);
    }

    private int dfs(TreeNode root, int targetSum, long sum) {
        if (root == null) {
            return 0;
        }
        sum += root.val;
        int count = sum == targetSum ? 1 : 0;
        count += dfs(root.left, targetSum, sum);
        count += dfs(root.right, targetSum, sum);
        return count;
    }

    public int pathSum(TreeNode root, int targetSum) {
        // 根到结点的总和 - 前缀和（根到这条线上的某一结点） = target
        if (root == null) {
            return 0;
        }
        this.target = targetSum;
        this.res = 0;
        map.put(0L, 1);
        dfsImp(root, 0);
        return res;
    }

    private void dfsImp(TreeNode root, long sum) {
        sum += root.val;
        if (map.containsKey(sum - target)) {
            res += map.get(sum - target);
        }
        // 前缀和
        map.put(sum, map.getOrDefault(sum, 0) + 1);
        if (root.left != null) {
            dfsImp(root.left, sum);
        }
        if (root.right != null) {
            dfsImp(root.right, sum);
        }
        map.put(sum, map.get(sum) - 1);
    }

    public int maxPathSum(TreeNode root) {
        maxGain(root);
        return maxSum;
    }

    private int maxGain(TreeNode root) {
        if (root == null) {
            return 0;
        }

        // 计算左右子树的最大路径和，为负数则不取
        int leftGain = Math.max(maxGain(root.left), 0);
        int rightGain = Math.max(maxGain(root.right), 0);

        // 当前结点的最大路径和
        int cur = root.val + leftGain + rightGain;

        maxSum = Math.max(cur, maxSum);
        // 同一个节点在一条路径序列中 至多出现一次 。
        return root.val + Math.max(leftGain, rightGain);

    }

    TreeNode head = new TreeNode(), cur = head;
    public TreeNode increasingBST(TreeNode root) {
        if (root == null) {
            return root;
        }
        // 中序遍历
        BST(root);
        return head.right;
    }

    private void BST(TreeNode root) {
        if (root == null) {
            return;
        }
        if (root.left != null) {
            BST(root.left);
        }
        cur.right = new TreeNode(root.val);
        cur = cur.right;
        if (root.right != null) {
            BST(root.right);
        }
    }

}